The basic notion of false-name-proofness allows for useful mechanisms under certain circumstances, but in general there are impossibility results that show that false-name-proof mechanisms have severe limitations. One may react to these impossibility results by saying that, since false-name-proof mechanisms are unsatisfactory, we should not run any important mechanisms in highly anonymous settings--unless, perhaps, we can find some methodology that directly prevents false-name manipulation even in such settings, so that we are back in a more typical mechanism design context. However, it seems unlikely that the phenomenon of false-name manipulation will disappear anytime soon. Because the Internet is so attractive as a platform for running certain types of mechanisms, it seems unlikely that the organizations running these mechanisms will take them offline. Moreover, because a goal of these organizations is often to get as many users to participate as possible, they will be reluctant to use high-overhead solutions that discourage users from participating. As a result, perhaps the most promising approaches at this point are those that combine techniques from mechanism design with other techniques discussed in this article.

This paper considers a mechanism design problem for locating two identical facilities on an interval, in which an agent can pretend to be multiple agents. A mechanism selects a pair of locations on the interval according to the declared single-peaked preferences of agents. An agent's utility is determined by the location of the better one (typically the closer to her ideal point). This model can represent various application domains. For example, assume a company is going to release two models of its product line and performs a questionnaire survey in an online forum to determine their detailed specs. Typically, a customer will buy only one model, but she can answer multiple times by logging onto the forum under several email accounts. We first characterize possible outcomes of mechanisms that satisfy false-name-proofness, as well as some mild conditions. By extending the result, we completely characterize the class of false-name-proof mechanisms when locating two facilities on a circle. We then clarify the approximation ratios of the false-name-proof mechanisms on a line metric for the social and maximum costs.

Combinatorial auctions are multiple-item auctions in which bidders may place bids on any package (subset) of goods. This additional expressibility produces benefits that have led to combinatorial auctions becoming extremely important both in practice and in theory. In the computer science community, auction design has focused primarily on computational practicality and incentive compatibility. The latter concerns mechanisms that are resistant to bidders misrepresenting themselves via a single false identity; however, with modern forms of bid submission, such as electronic bidding, other types of cheating have become feasible. Prominent amongst them is false-name bidding; that is, bidding under pseudonyms. For example, the ubiquitous Vickrey-Clarke-Groves (VCG) mechanism is incentive compatible and produces optimal allocations, but it is not false-name-proof–bidders can increase their utility by submitting bids under multiple identifiers. Thus, there has recently been much interest in the design and analysis of false-name-proof auction mechanisms. These false-name-proof mechanisms, however, have polynomially small efficiency guarantees: they can produce allocations with very low economic efficiency/social welfare. In contrast, we show that, provided the degree to which different goods are complementary is bounded (as is the case in many important, practical auctions), the VCG mechanism gives a constant efficiency guarantee. Constant efficiency guarantees hold even at equilibria where the agents bid in a manner that is not individually rational. Thus, while an individual bidder may personally benefit greatly from making false-name bids, this will have only a small detrimental effect on the objective of the auctioneer: maximizing economic efficiency. So, from the auctioneer's viewpoint the VCG mechanism remains preferable to false-name-proof mechanisms.

The basic notion of false-name-proofness allows for useful mechanisms under certain circumstances, but in general there are impossibility results that show that false-name-proof mechanisms have severe limitations. One may react to these impossibility results by saying that, since false-name-proof mechanisms are unsatisfactory, we should not run any important mechanisms in highly anonymous settings--unless, perhaps, we can find some methodology that directly prevents false-name manipulation even in such settings, so that we are back in a more typical mechanism design context. Because the Internet is so attractive as a platform for running certain types of mechanisms, it seems unlikely that the organizations running these mechanisms will take them offline. As a result, perhaps the most promising approaches at this point are those that combine techniques from mechanism design with other techniques discussed in this article.